#include <iostream>
#include <stdio.h> 
#include <stdlib.h>  
#include <math.h>  
#include <ctype.h>  
#include <time.h>  
#include <queue> 

#include <unistd.h> 
#include "assert.h"
using namespace std;  
#define INF (0x23333333)  
#define MAXN (302) 
#define random(x) (rand()%x) 
  
//寻四方向用  
const int dl[] = {1,-1,0,0};  
const int dc[] = {0,0,-1,1};  
  
int map[MAXN][MAXN]; //地图  
int n,m;   //地图的行数列数  
int g[MAXN][MAXN]; //已用代价，参数为行列坐标  
int h[MAXN][MAXN]; //估计还需代价，参数为行列坐标  
bool in_close[MAXN][MAXN]; //在关闭列表中，参数为行列坐标  
bool in_open[MAXN][MAXN]; //在开启列表中，参数为行列坐标  
//bool ok = false;  //立一个找到解的flag  
struct point  
{  
    int l,c;  
    point(){}  
    point(int _l, int _c){l=_l;c=_c;}  
    bool operator<(const point &o) const  
    {  
        return g[l][c]+h[l][c]>g[o.l][o.c]+h[o.l][o.c];  
        //启发数值在优先队列里面从小到大...  
    }  
};  
point path[MAXN][MAXN];  //记录路径用  


int sl,sc; //出发/目标点的位置  
int tl1,tl2,tl3,tl4,tl5,tc1,tc2,tc3,tc4,tc5;
int z_sl,z_sc;
int z_tl1,z_tl2,z_tl3,z_tl4,z_tl5,z_tc1,z_tc2,z_tc3,z_tc4,z_tc5;


 void msleep(int ms)  
{  
    struct timeval delay;  
    delay.tv_sec = 0;  
    delay.tv_usec = ms * 1000; 
    select(0, NULL, NULL, NULL, &delay);  
}  
    
void find_path(int  tl, int tc ,int sl,int sc,int sp )  
{  
	
	int i,j;  
    int cl,cc,nl,nc; 
      
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      path[i][j]=point(i,j);//初始化路径
    
   for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
	 		 in_close[i][j] = false;  //初始化关闭列表
	 
	
    priority_queue<point> open_list;  
   
    for(i = 1; i <= n; i++)  
    {  
        for(j = 1; j <= m; j++)  
        {  
            h[i][j] = (int)sqrt((double)(i-tl)*(i-tl)+(double)(j-tc)*(j-tc))+1;  
            g[i][j] = INF;  
        }  
    }  
    g[sl][sc] = 0;  
    in_open[sl][sc] = true;  
    open_list.push(point(sl,sc));  
	
      
    while(open_list.size())  
      
   
    {  
        cl = open_list.top().l;  
        cc = open_list.top().c;  
        open_list.pop();  
        if(cl == tl && cc == tc)  
        {  
           
            break;  
        }
       
        in_close[cl][cc] = true;  
        for(i = 0; i < 4; i++)  
        {  
            nl = cl+dl[i];  
            nc = cc+dc[i];  
            if(map[nl][nc]!=0&&map[nl][nc]!=sp)continue; 
            if(in_close[nl][nc])continue;  
            if(! in_open[nl][nc])  
            {   
                open_list.push(point(nl,nc));  
            }else if(g[cl][cc]+1 >= g[nl][nc])  
                continue; 
                  
            
            path[nl][nc] = point(cl,cc);  
            g[nl][nc] = g[cl][cc] + 1;  
        }  
    }  
}  
  
void print_res()  
{  
      
    int i,j;  
    
    for(i = 0; i <= n+1; i++)  
    {  
        for(j = 0; j <= m+1; j++)  
        {  
            switch(map[i][j])
            {
            	case 0:printf(" ");break;
            	case 1:printf("\033[41m1\033[m");break;
            	case 2:printf("\033[41m2\033[m");break;
            	case 3:printf("\033[41m3\033[m");break;
            	case 4:printf("\033[41m4\033[m");break;
				case 21:printf("\033[42mA\033[m");break;
				case 22:printf("\033[42mB\033[m");break;
				case 23:printf("\033[42mC\033[m");break;
				case 24:printf("\033[42mD\033[m");break;
            	case 6:printf("#");break;
            	default:break;
            } 
        }  
        putchar('\n');  
    }  
       
         
}  


int GetMax()
{

   int i,j;
   int max=0;
   for(i = 1; i <= n; i++)  
   for(j = 1; j <= m; j++)  
     if( map[i][j]<6&&map[i][j]>=max)
                   max=map[i][j];
              return max;            
}

int GetMax2()
{

   int i,j;
   int max=20;
   for(i = 1; i <= n; i++)  
   for(j = 1; j <= m; j++)  
   {
     if( map[i][j]>6&&map[i][j]>=max)
                   max=map[i][j];
				
   }	
   return max; 
}

bool Appeared(int a)
{
	int i,j,p=0;
    for(i = 1; i <= n; i++)  
    for(j = 1; j <= m; j++) 
     
         if(map[i][j]==a)
               p=1;
               if(p==1) return 1;
			   else return 0;
                   
}

void Clear(int a)
{
	int i,j;
    for(i = 1; i <= n; i++)  
    for(j = 1; j <= m; j++)  
         if( map[i][j]==a)
           map[i][j]=0;

}

  
int main()  
{  
	 int i, j, z;
	 n=20,m=40,z=100;
     int l,c;
     int x,y;
     int count=0;
     int MaxNumber;
	 int MaxNumber2;
	 int q;
    
     tl1=n; z_tl1=1;
	 tl2=n; z_tl2=1;
	 tl3=n; z_tl3=1;
	 tl4=n; z_tl4=1;
	 tl5=n; z_tl5=1;
     tc1=m; z_tc1=1;
	 tc2=m; z_tc2=1;
	 tc3=m; z_tc3=1;
	 tc4=m; z_tc4=1;
	 tc5=m; z_tc5=1;
	 bool finished=false;
	 bool finished2=false;
     sl=1,sc=1;
     z_sl=n,z_sc=m;
     
	
     
	 srand((int)time(0));
	for(int i=0;i<=n+1;i++)
		for(int j=0;j<=m+1;j++)
		{
			if(i==0|j==0|i==n+1|j==m+1)
				map[i][j]=6;
			else if(i>=1&&i<=5&&j>=1&&j<=2||i>=n-5&&i<=n&&j>=m-2&&j<=m)
				map[i][j]=0;
			else
			{
				int x=random(50);
				if(x<=1)
					map[i][j]=6;
				else
					map[i][j]=0;	
			}
		}		
    
    while(true)
    {  
    	printf("\033[2J");
    	++count;
    	MaxNumber=GetMax();
		MaxNumber2=GetMax2();

     if((map[n][m]==0)&&(finished==false))
	 {
        map[n][m]=MaxNumber+1;
		if(map[n][m]==5) finished=true;
	 }
	 if((map[1][1]==0)&&(finished2==false))
	 {     map[1][1]=MaxNumber2+1;
		if(map[1][1]==25) finished2=true;
	 }
	 
	 
	 
      if((count>16)&&((count-16)%2==0)&&(Appeared(4)==1)&&(!((tl4==sl)&&(tc4==sc)))) 
        {  
        	
          
       
   
		   find_path(tl4,tc4,1,1,4);
           x = path[tl4][tc4].l; 
           y = path[tl4][tc4].c;  
		   cout<<"x4 y4  "<<x<<"  "<<y<<endl;
           Clear(4);
            map[x][y]=4;
           tl4=x;
           tc4=y;
		   
		   
		   
        }
	 
     if((count>12)&&((count-12)%3==0)&&(Appeared(3)==1)&&(!((tl3==sl)&&(tc3==sc)))) 
        {  
        	
           
        
           l = tl3;  
           c = tc3;
		    
          find_path(tl3,tc3,1,1,3);
           x = path[l][c].l; 
           y = path[l][c].c; 
			cout<<"x3 y3  "<<x<<"  "<<y<<endl;
           l = x;             
           c = y ;         
           Clear(3);
          map[l][c]=3;
           tl3=l;
           tc3=c;
        }
   
   if((count>1)&&((count-1)%5==0)&&(Appeared(1)==1)&&(!((tl1==sl)&&(tc1==sc)))) 
       {  
       	    
           
           
             
     
           l = tl1;  
           c = tc1;   
		   
		  find_path(tl1,tc1,1,1,1);
           
           x = path[l][c].l; 
           y = path[l][c].c;
		cout<<"x1 y1  "<<x<<"  "<<y<<endl;		   
           l = x;             
           c = y;        
           Clear(1);
           map[l][c]=1;
           tl1=l;
           tc1=c;
           
		  
      } 
        
		if((count>7)&&((count-7)%4==0)&&(Appeared(2)==1)&&(!((tl2==sl)&&(tc2==sc)))) 
        {  
        	
           
      
           l = tl2;  
           c = tc2;
		     find_path(tl2,tc2,1,1,2);
		  
		   
           x = path[l][c].l; 
           y = path[l][c].c;  
		   cout<<"x2 y2  "<<x<<"  "<<y<<endl;
           l = x;             
           c = y ;         
           Clear(2);
            map[l][c]=2;
           tl2=l;
           tc2=c;
        }
		
		//-------------------------
		if((count>16)&&((count-16)%2==0)&&(Appeared(24)==1)&&(!((z_tl4==z_sl)&&(z_tc4==z_sc))))
        {  
        	 
		   l = z_tl4;  
           c = z_tc4;		    
		   find_path(z_tl4,z_tc4,n,m,24);
           x = path[l][c].l; 
           y = path[l][c].c;  
		   cout<<"xD yD  "<<x<<"  "<<y<<endl;
           l = x;             
           c = y ;         
           Clear(24);
           map[l][c]=24;
           z_tl4=l;
           z_tc4=c;   	      	   
        }
		if((count>12)&&((count-12)%3==0)&&(Appeared(23)==1)&&(!((z_tl3==z_sl)&&(z_tc3==z_sc))))
        {  
		   l = z_tl3;  
           c = z_tc3;		    
		   find_path(z_tl3,z_tc3,n,m,23);
           x = path[l][c].l; 
           y = path[l][c].c; 
			cout<<"xC yC  "<<x<<"  "<<y<<endl;		   
           l = x;             
           c = y ;         
           Clear(23);
           map[l][c]=23;
           z_tl3=l;
           z_tc3=c;   	      	   
        }
		if((count>7)&&((count-7)%4==0)&&(Appeared(22)==1)&&(!((z_tl2==z_sl)&&(z_tc2==z_sc))))
        {  
        	 
		   l = z_tl2;  
           c = z_tc2;		    
		   find_path(z_tl2,z_tc2,n,m,22);
           x = path[l][c].l; 
           y = path[l][c].c; 
			cout<<"xB yB  "<<x<<"  "<<y<<endl;		   
           l = x;             
           c = y ;         
           Clear(22);
           map[l][c]=22;
           z_tl2=l;
           z_tc2=c;   	      	   
        }
		if((count>1)&&((count-1)%5==0)&&(Appeared(21)==1)&&(!((z_tl1==z_sl)&&(z_tc1==z_sc))))
        {  
        	 
		   l = z_tl1;  
           c = z_tc1;		    
		   find_path(z_tl1,z_tc1,n,m,21);
           x = path[l][c].l; 
           y = path[l][c].c; 
			cout<<"xA yA  "<<x<<"  "<<y<<endl;
           l = x;             
           c = y ;         
           Clear(21);
           map[l][c]=21;
           z_tl1=l;
           z_tc1=c;   	      	   
        }
      print_res();
      if(map[1][1]==1&&map[n][m]==21){ break;
	  cout<<"Game over!!"<<endl;}
	  
      msleep(200);
    
    
    	
    }
    return 0;  
}
